Pricing bridges to cross a river

We consider a pricing problem in directed, uncapacitated networks. Tariffs must be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs in the network are assumed to be given. There are n clients, the followers, and after the tariffs have been determined, the clients route their demands independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator's revenue. Motivated by applications in telecommunication networks, we consider a restricted version of this problem, assuming that each client utilizes at most one of the operator's tariff arcs. The problem is equivalent to pricing bridges that clients can use in order to cross a river. We prove that this problem is APX‐hard. Moreover, we analyze the effect of uniform pricing, proving that it yields both an m approximation and a (1 + lnD)‐approximation. Here, D is upper bounded by the total demand of all clients. In addition, we consider the problem under the additional restriction that the operator must not reject any of the clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless P = NP, and we prove the existence of an n‐approximation algorithm. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

双绝热近似下磁流体力学线性稳定性原理

本文得出了双绝热近似的磁流体力学能量积分关系式。分析表明这种磁流体力学系统是保守的,可以采用运动方程或能量原理方法分析系统的稳定性特性。本文从控制方程组出发讨论了线性稳定性的基本原理,指出纵向压力增值有助于系统的稳定性。     

The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998     

导弹光学告警系统及对抗技术综述

详述了导弹羽烟热辐射的光电高速采集方法 ,并实时对导弹逼近告警。同时介绍了国外红外告警技术的发展现状     

目标宽频带RCS的快速算法研究

目标宽带RCS预估算法一直是计算电磁学的一个研究热点，本文分别研究了渐近波形估计技术（AWE）与最佳一致逼近技术在宽频带RCS预估领域内的应用。首先，介绍了传统矩量法计算RCS的原理，并分析了两种快速算法的计算过程。然后，采用这两种技术，分别计算了简易飞机模型的RCS值，并对这两种方法进行比较。计算结果表明相比传统的矩量法，这两种方法在不影响精度的前提下大大提高了计算效率。同时，相比渐近波形估计技术，最佳一致逼近技术在节省内存，节约时间方面更具优势。最后，采用最佳一致逼近理论，结合电磁计算软件，实现较大尺寸目标的宽频带RCS的计算。     

Single‐machine scheduling with deadlines to minimize the total weighted late work

We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP‐hard even if all the jobs have a unit weight, (ii) the problem is binary NP‐hard and admits a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.     

融合初值校准与二阶逼近的单星测频定位算法

为减小单星测频定位的误差,提出一种融合初值校准与二阶逼近的单星测频定位算法。该算法在卫星接收信号多普勒频移为零的时间点,通过测距获得卫星到定位目标的距离信息,利用距离信息修正轨道平面与定位目标的几何关系,为初值的选取提供校准手段;将校准的初值代入含二阶级数的定位方程泰勒展开式,通过较少次数的迭代得到定位目标的真实位置,从而降低定位的算法复杂度,提高定位精度。仿真结果表明,所提出的算法与多普勒单星定位算法相比,迭代次数和定位误差大幅度减小,其实现简单、计算量少、误差小,在单星定位研究领域具有较高的理论价值和实用价值。     

Optimizing natural gas pipeline transmission with nonuniform elevation: A new initialization approach

In this paper, we develop an iterative piecewise linear approximation approach with a novel initialization method to solve natural gas pipeline transmission problems with the nonuniform network elevation. Previous approaches, such as energy minimization methods, cannot be applied to solve problems with the nonuniform network elevation because they exclude pressure range constraints, and thus provide solutions far from optimum. We propose a new initialization model that considers pressure range constraints and improves the optimality of the solutions and the computational efficiency. Furthermore, we extend the energy minimization methods and provide the necessary conditions under which the extended methods operate in networks with the nonuniform elevation. We test the performances of the methods with previously reported pipeline networks from the literature, with the open data set GasLib, and with our industrial collaborator. The initialization approach is shown to be more efficient than the method with fixed initial breakpoints. The newly proposed initialization approach generates solutions with a higher accuracy than the extended energy minimization methods, especially in large‐size networks. The proposed method has been applied to natural gas transmission planning by the China National Petroleum Corporation and has brought a direct profit increase of 330 million U.S. dollars in 2015‐2017.     

Approximation algorithms for general one‐warehouse multi‐retailer systems

Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross‐docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε‐optimality can be obtained by solving a related piece‐wise linear concave cost multi‐commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece‐wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece‐wise concavity feature of the cost functions. This gives rise to a unified and generic LP‐based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

弹性轨道磁悬浮控制系统模型降阶研究

在磁悬浮控制系统中,常常忽略轨道的弹性来设计控制算法。在这种控制算法作用下,当轨道刚度较小时,系统容易产生振动。为解决该问题,可以将轨道弹性加入悬浮模型,然后设计控制算法。考虑轨道弹性之后,悬浮系统的模型会比较复杂,控制算法难以在工程实现。为此,采用Hankel范数近似法对考虑轨道弹性后的模型进行降阶,并且在降阶模型的基础上设计控制算法,解决了轨道弹性引发的系统振动问题。并且,这种方法容易在工程中实现。文章最后利用仿真结果验证了降阶方法的可行性。